#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType val;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
    int flag; // 用于标记遍历状态
} BTNode;
// 前序遍历NLR
void pre_recurse(BTNode *root)
{
    if (root == NULL)
        return;

    cout << root->val << " ";
    pre_recurse(root->left);
    pre_recurse(root->right);
}
void pre_nonrecurse1(BTNode *root)
{
    if (!root)
        return;
    stack<BTNode *> st;
    st.push(root);
    while (!st.empty())
    {
        BTNode *top = st.top();
        st.pop();
        cout << top->val << " ";
        if (root->right)
            st.push(root->right);
        if (root->left)
            st.push(root->left);
    }
}
void pre_nonrecurse2(BTNode *root)
{
    stack<BTNode *> st;
    BTNode *cur = root;
    while (cur || !st.empty())
    {
        // 遍历到最左结点
        while (cur)
        {
            cout << cur->val << " ";
            st.push(cur);
            cur = cur->left;
        }
        // 栈顶结点出栈 访问栈顶结点的右子树
        BTNode *top = st.top();
        st.pop();
        cur = top->right;
    }
}

// 中序遍历LNR
void InOrder(BTNode *root)
{
    if (root == NULL)
        return;

    InOrder(root->left);
    cout << root->val << " ";
    InOrder(root->right);
}
void in_nonrecurse(BTNode *root)
{
    stack<BTNode *> st;
    BTNode *cur = root;
    while (cur || !st.empty())
    {
        while (cur)
        {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        cout << cur->val << " ";
        cur = cur->right;
    }
}

// 后序遍历LRN
void PostOrder(BTNode *root)
{
    if (root == NULL)
        return;

    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->val << " ";
}
vector<int> post_nonrecurse(BTNode *root)
{
    vector<int> v;
    stack<BTNode *> st;
    BTNode *cp = root;
    BTNode *prv = nullptr;

    while (cp || !st.empty())
    {
        while (cp)
        {
            st.push(cp);
            cp = cp->left;
        }

        BTNode *top = st.top();
        // 左已经为空 若右也空 左右已遍历结束 需要访问根
        if (top->right == nullptr || top->right == prv)
        {
            prv = top;             // 记录当前所访问结点
            v.push_back(top->val); // 访问数据
            st.pop();              // 出栈
        }
        else
            cp = top->right;

        // cp仍指向该结点的左孩子(null)
    }

    return v;
};
vector<int> post_reverse(BTNode *root)
{
    if (root == nullptr)
        return {};

    vector<int> v;
    stack<BTNode *> st;
    st.push(root);

    while (!st.empty())
    {
        BTNode *top = st.top();
        st.pop();

        if (top != nullptr)
            v.push_back(top->val);
        else
            continue;

        st.push(top->left);
        st.push(top->right);
    }

    reverse(v.begin(), v.end());
    return v;
}
void post_flag(BTNode *root)
{
    if (root == nullptr)
        return;

    std::stack<BTNode *> st;
    BTNode *cp = root;

    while (cp || !st.empty())
    {
        // 一路遍历并记录指针到最左结点
        while (cp)
        {
            st.push(cp);
            cp->flag++; // 表示左子树已被遍历
            cp = cp->left;
        }

        cp = st.top();
        if (cp->flag == 2)
        { // 左右子树都被遍历
            // 访问
            std::cout << " " << cp->val;
            // 出栈
            st.pop();

            // cp 置空表示当前子树已被访问完
            // 需要访问下一个栈顶即上一个结点
            cp = nullptr;
        }
        else
        {
            cp->flag++;
            cp = cp->right;
        }
    }
}

// 创建新结点
BTNode *CreatNode(BTDataType x)
{
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    assert(node);

    node->val = x;
    node->left = NULL;
    node->right = NULL;

    return node;
}

// 自创二叉树
BTNode *CreatBinaryTree()
{
    BTNode *nodeA = CreatNode('A');
    BTNode *nodeB = CreatNode('B');
    BTNode *nodeC = CreatNode('C');
    BTNode *nodeD = CreatNode('D');
    BTNode *nodeE = CreatNode('E');
    BTNode *nodeF = CreatNode('F');
    BTNode *nodeG = CreatNode('G');
    BTNode *nodeH = CreatNode('H');
    BTNode *nodeI = CreatNode('I');

    nodeA->left = nodeB;
    nodeA->right = nodeC;

    nodeB->left = nodeD;
    nodeB->right = nodeF;

    nodeF->left = nodeE;

    nodeC->left = nodeG;
    nodeC->right = nodeI;

    nodeG->right = nodeH;

    return nodeA;
}

// 结点个数1.0--NLR

void TreeSize1(BTNode *root, int &count)
{
    if (root == NULL)
    {
        return;
    }

    ++count;
    TreeSize1(root->left, count);
    TreeSize1(root->right, count);
}

// 结点个数2.0--LRN
int TreeSize2(BTNode *root)
{
    return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

// 叶子结点数--LRN
int TreeLeafSize(BTNode *root)
{
    if (root == NULL)
        return 0;

    if (root->left == NULL && root->right == NULL)
        return 1;

    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

// 第k层结点个数--LRN
int TreeKLevel(BTNode *root, int k)
{
    assert(k >= 1);

    if (root == NULL)
        return 0;

    if (k == 1)
        return 1;

    return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

// 求二叉树深度--LRN
int TreeDepth(BTNode *root)
{
    if (root == NULL)
        return 0;

    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);

    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

// 查找目标结点--NLR
BTNode *TreeFind(BTNode *root, BTDataType x)
{
    if (root == NULL)
        return NULL;

    if (root->val == x)
        return root;

    BTNode *ret1 = TreeFind(root->left, x);
    if (ret1)
        return ret1;
    BTNode *ret2 = TreeFind(root->right, x);
    if (ret2)
        return ret2;

    return NULL;
}
// g++ traverse.cc -o test -std=c++11
int main()
{
    // 创建二叉树
    BTNode *root = CreatBinaryTree();
    // NLR
    pre_recurse(root);
    printf("\n");
    // LNR
    InOrder(root);
    printf("\n");
    // LRN
    PostOrder(root);
    printf("\n");

    // 结点个数1.0
    int count = 0;
    TreeSize1(root, count);
    printf("TreeSize:%d\n", count);

    // 结点个数2.0
    printf("TreeSize:%d\n", TreeSize2(root));
    printf("TreeSize:%d\n", TreeSize2(root));

    // 叶子结点数
    printf("LeafSize:%d\n", TreeLeafSize(root));

    // 第k层结点个数
    printf("KLevelSize:%d\n", TreeKLevel(root, 1));
    printf("KLevelSize:%d\n", TreeKLevel(root, 2));
    printf("KLevelSize:%d\n", TreeKLevel(root, 3));
    printf("KLevelSize:%d\n", TreeKLevel(root, 4));

    return 0;
}
